package cn.icatw.leetcode.editor.cn;
//给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
//
// 你可以按 任何顺序 返回答案。
//
//
//
// 示例 1：
//
//
//输入：n = 4, k = 2
//输出：
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [1,2],
//  [1,3],
//  [1,4],
//]
//
// 示例 2：
//
//
//输入：n = 1, k = 1
//输出：[[1]]
//
//
//
// 提示：
//
//
// 1 <= n <= 20
// 1 <= k <= n
//
//
// Related Topics 回溯 👍 1646 👎 0


import java.util.ArrayList;
import java.util.List;

//Java：组合
public class T77_Combinations {
    public static void main(String[] args) {
        Solution solution = new T77_Combinations().new Solution();
        // TO TEST
        solution.combine(4, 2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> result = new ArrayList<>();
            backtrack(result, new ArrayList<>(), n, k, 1);
            return result;
        }

        private void backtrack(List<List<Integer>> result, List<Integer> tempList, int n, int k, int start) {
        //如果当前组合的长度等于k，则将其加入到结果集中
            if (tempList.size() == k) {
                result.add(new ArrayList<>(tempList));
                return;
            }
            //从start开始遍历
            for (int i = start; i <= n; i++) {
                tempList.add(i);
                //递归
                backtrack(result, tempList, n, k, i + 1);
                //回溯
                tempList.remove(tempList.size() - 1);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
